package ua.mykola.dynamicp;

public class LongestIncreasingSubsequence
{

    public int length(int[] sequence)
    {
        int[] l = new int[sequence.length];
        l[0] = 1;
        for (int i = 1; i < sequence.length; i++)
        {
            int currentLength = 1;
            for (int j = 0; j <= i; j++)
            {
                if ((l[j] >= currentLength) && (sequence[i] > sequence[j]))
                {
                    currentLength = l[j] + 1;
                }
            }
            l[i] = currentLength;
        }

        return getMax(l);
    }

    private int getMax(int[] l)
    {
        int largest = l[0];
        for (int i = 1; i < l.length; i++)
        {
            largest = Math.max(largest, l[i]);
        }
        return largest;
    }

}
